import Util.ListNode;

/**
 * 两个单链表的交点
 */
public class Solution52 {

    public ListNode findFirstCommonNode1(ListNode pHead1, ListNode pHead2){
        ListNode l1 = pHead1, l2 = pHead2;
        while (l1 != l2){
            l1 = (l1 == null) ? pHead2 : l1.next;
            l2 = (l2 == null) ? pHead1 : l2.next;
        }
        return l1;
    }

    public ListNode findFirstCommonNode2(ListNode pHead1, ListNode pHead2){
        int length1 = getLength(pHead1);
        int length2 = getLength(pHead2);

        int difLength = length1 - length2;
        ListNode listLong = pHead1;
        ListNode listShort = pHead2;

        if (length1 < length2){
            difLength = length2 - length1;
            listLong = pHead2;
            listShort = pHead1;
        }

        for (int i = 0; i < difLength; i++){
            listLong = listLong.next;
        }

        while (listLong != listShort){
            listLong = listLong.next;
            listShort = listShort.next;
        }

        return listLong;
    }

    private int getLength(ListNode pHead){
        int length = 0;
        while (pHead != null){
            ++length;
            pHead = pHead.next;
        }
        return length;
    }
}
